Chapter 01: What is Recursion?

The Recursive Mindset: Solving Problems by Solving Smaller Versions

Imagine you're standing in a long hallway with 100 doors. Your task: count how many doors there are. You could walk down the hall, pointing at each door: "One, two, three..." But there's another way to think about this problem—a way that might seem strange at first, but reveals a powerful pattern of thought.

Instead of counting all 100 doors yourself, you could: 1. Count the first door (that's 1) 2. Ask someone else to count the remaining 99 doors 3. Add your count to theirs: 1 + (their answer)

This is recursive thinking: solving a problem by solving a smaller version of the same problem.

But wait—who counts those 99 doors? Someone who uses the exact same strategy: 1. Count the first door (that's 1) 2. Ask someone else to count the remaining 98 doors 3. Add: 1 + (their answer)

This chain continues until someone reaches a hallway with just 1 door. They don't need to ask anyone—they can answer directly: "There's 1 door." This answer flows back up the chain, and everyone adds their 1 to it.

This is the essence of recursion: a function that calls itself with a simpler version of the original problem, until it reaches a case so simple it can answer directly.

From Concept to Code: Counting Down

Let's see this mindset in action with the simplest possible recursive function: counting down from a number to zero.

The Problem: Print all numbers from n down to 0.

The Recursive Insight: - To count down from 5, first print 5, then count down from 4 - To count down from 4, first print 4, then count down from 3 - ... - To count down from 0, just print 0 (no more counting needed)

Let's implement this:

def countdown(n):
    """Print numbers from n down to 0."""
    print(n)
    countdown(n - 1)

# Let's try it
countdown(3)

Python Output:

3
2
1
0
-1
-2
-3
...
[continues forever until...]
RecursionError: maximum recursion depth exceeded while calling a Python object

Diagnostic Analysis: Understanding the Failure

The complete execution trace (first few calls):

countdown(3)
  → print 3
  → countdown(2)
    → print 2
    → countdown(1)
      → print 1
      → countdown(0)
        → print 0
        → countdown(-1)
          → print -1
          → countdown(-2)
            → print -2
            → countdown(-3)
              ... [continues indefinitely]

Let's parse this section by section:

The error message: RecursionError: maximum recursion depth exceeded
What this tells us: Python has a safety limit on how many times a function can call itself (default: 1000 calls)
We hit that limit, meaning our function never stopped calling itself
The call stack depth:
Current depth: 1000+ (Python's limit)
Expected depth: 4 (for countdown(3): calls at 3, 2, 1, 0)
Key observation: The function kept calling itself even after reaching 0
Variable values at failure: n = -997, -998, -999, ... (kept decreasing forever)
What this tells us: The parameter n kept decreasing past 0
Critical insight: We never told the function when to STOP
The recursive call pattern:
Expected: countdown(3) → countdown(2) → countdown(1) → countdown(0) → STOP
Actual: countdown(3) → countdown(2) → countdown(1) → countdown(0) → countdown(-1) → countdown(-2) → ...
Key difference: No stopping condition

Root cause identified: The function has no base case—no condition that says "stop recursing."

Why the current approach can't solve this: Every recursive function needs two parts: 1. Recursive case: The part that calls itself with a simpler problem 2. Base case: The stopping condition that answers directly without recursing

What we need: A condition that detects when we've reached the simplest case (n = 0) and stops there.

Iteration 1: Adding the Base Case

Before (Iteration 0):

def countdown(n):
    print(n)
    countdown(n - 1)  # Always recurses, never stops

Problem: No stopping condition—infinite recursion.

After (Iteration 1):

def countdown(n):
    """Print numbers from n down to 0."""
    if n < 0:  # ← BASE CASE: Stop when we go negative
        return
    print(n)
    countdown(n - 1)  # ← RECURSIVE CASE: Solve smaller problem

# Test it
countdown(3)

Python Output:

Success! The function now terminates correctly.

Call Stack Visualization:

countdown(3)
  → n=3, not < 0, so print 3
  → countdown(2)
    → n=2, not < 0, so print 2
    → countdown(1)
      → n=1, not < 0, so print 1
      → countdown(0)
        → n=0, not < 0, so print 0
        → countdown(-1)
          → n=-1, IS < 0, so return (BASE CASE HIT!)
        ← returns to countdown(0)
      ← returns to countdown(1)
    ← returns to countdown(2)
  ← returns to countdown(3)
Done!

What changed: We added a base case that checks if n < 0 and returns immediately without making another recursive call. This breaks the infinite chain.

The Two Essential Parts of Every Recursive Function

Every recursive function must have:

Base Case(s): The stopping condition(s)
Detects when the problem is simple enough to solve directly
Returns a result without recursing
Prevents infinite recursion
Recursive Case: The self-reference
Calls the function itself with a simpler/smaller version of the problem
Must make progress toward the base case
Combines the result of the recursive call into the final answer

Critical Rule: The recursive case must always move toward the base case. In countdown(n), we call countdown(n - 1), which decreases n and moves us closer to n < 0.

The Recursive Mindset in Action

Let's trace countdown(3) by hand to internalize the pattern:

Manual Trace:

countdown(3)
  → Is 3 < 0? No
  → Print 3
  → Call countdown(2)

    countdown(2)
      → Is 2 < 0? No
      → Print 2
      → Call countdown(1)

        countdown(1)
          → Is 1 < 0? No
          → Print 1
          → Call countdown(0)

            countdown(0)
              → Is 0 < 0? No
              → Print 0
              → Call countdown(-1)

                countdown(-1)
                  → Is -1 < 0? YES! BASE CASE
                  → Return immediately

              ← countdown(0) finishes

          ← countdown(1) finishes

      ← countdown(2) finishes

  ← countdown(3) finishes

Program ends

Key Insight: Each function call waits for the recursive call to complete before it can finish. They stack up, then unwind in reverse order.

Why This Matters: The Power of Self-Reference

Recursion might seem like an odd way to count down—why not just use a loop? Fair question. But notice what we've done: we've defined counting down in terms of itself. This self-referential definition is surprisingly powerful for certain types of problems.

Consider: "How do you count down from n?" - Iterative answer: "Start at n, subtract 1, repeat until you reach 0" - Recursive answer: "Print n, then count down from n-1"

The recursive answer is more declarative—it describes what counting down means rather than how to do it step-by-step. For simple problems like this, iteration is clearer. But for complex problems involving hierarchical structures (trees, nested data, divide-and-conquer algorithms), the recursive definition often maps more naturally to the problem structure.

Common Beginner Confusion: "But Where Does It Stop?"

A common question: "If countdown(3) calls countdown(2), which calls countdown(1), which calls countdown(0), which calls countdown(-1)... how does it know to stop?"

Answer: The base case (if n < 0: return) is checked at the start of every call. When countdown(-1) is called, the very first thing it does is check if -1 < 0, which is true, so it returns immediately without printing or recursing further.

Think of the base case as a guard at the entrance of the function: "Before you do anything else, check if you're in a situation where you should just return immediately."

Anatomy of a Recursive Function

Now that we've seen recursion in action, let's dissect the structure of a recursive function systematically. We'll build a more interesting example: calculating the factorial of a number.

The Problem: Calculate n! (n factorial) = n × (n-1) × (n-2) × ... × 2 × 1

For example: - 5! = 5 × 4 × 3 × 2 × 1 = 120 - 3! = 3 × 2 × 1 = 6 - 1! = 1 - 0! = 1 (by mathematical definition)

The Recursive Insight: - 5! = 5 × 4! - 4! = 4 × 3! - 3! = 3 × 2! - 2! = 2 × 1! - 1! = 1 (base case)

Notice the pattern: n! = n × (n-1)!

This is a recursive definition—factorial is defined in terms of itself.

Phase 1: The Reference Implementation

Let's implement factorial recursively:

def factorial(n):
    """Calculate n! = n × (n-1) × ... × 2 × 1"""
    # BASE CASE: The simplest case we can solve directly
    if n == 0 or n == 1:
        return 1

    # RECURSIVE CASE: Break down into smaller problem
    return n * factorial(n - 1)

# Test it
print(f"5! = {factorial(5)}")
print(f"3! = {factorial(3)}")
print(f"1! = {factorial(1)}")
print(f"0! = {factorial(0)}")

Python Output:

5! = 120
3! = 6
1! = 1
0! = 1

Perfect! Let's break down the anatomy of this function.

The Three Components of a Recursive Function

1. The Function Signature

def factorial(n):
    """Calculate n! = n × (n-1) × ... × 2 × 1"""

Parameter(s): The input that defines the problem size (n)
Return value: The solution to the problem (the factorial result)
Docstring: Describes what the function computes

Key principle: The parameter must be something that can be made "smaller" or "simpler" in the recursive call.

2. The Base Case(s)

if n == 0 or n == 1:
        return 1

Purpose: Define the stopping condition—the simplest case that can be solved without recursion.

Characteristics: - Checked first, before any recursive calls - Returns a concrete value directly - No recursive call inside the base case - Must be reachable from any valid input

Why two conditions? Both 0! and 1! equal 1 by definition. We could write this as just if n <= 1: return 1, but being explicit about both cases makes the mathematical definition clearer.

Critical: Every possible input must eventually reach a base case. If not, you get infinite recursion.

3. The Recursive Case

return n * factorial(n - 1)

Purpose: Break the problem into a smaller version of itself and combine the result.

Characteristics: - Calls the function itself with a simpler argument - Must make progress toward the base case (here: n - 1 moves toward 0) - Combines the recursive result with current work (here: multiply by n)

The Trust Principle: When writing the recursive case, assume the recursive call works correctly. Don't try to trace through all the levels—trust that factorial(n-1) will correctly return (n-1)!. Your job is just to use that result to compute n!.

Visualizing the Execution: Call Stack Trace

Let's trace factorial(5) to see how these components work together:

Execution Trace:

factorial(5)
  → Is 5 == 0 or 5 == 1? No
  → Return 5 * factorial(4)

    factorial(4)
      → Is 4 == 0 or 4 == 1? No
      → Return 4 * factorial(3)

        factorial(3)
          → Is 3 == 0 or 3 == 1? No
          → Return 3 * factorial(2)

            factorial(2)
              → Is 2 == 0 or 2 == 1? No
              → Return 2 * factorial(1)

                factorial(1)
                  → Is 1 == 0 or 1 == 1? YES! BASE CASE
                  → Return 1

              ← 2 * 1 = 2
              ← Return 2

          ← 3 * 2 = 6
          ← Return 6

      ← 4 * 6 = 24
      ← Return 24

  ← 5 * 24 = 120
  ← Return 120

Result: 120

Key Observations:

The descent: Calls stack up as we recurse down to the base case
The base case: factorial(1) returns immediately without recursing
The ascent: Results flow back up, each level computing its result from the level below
The combination: Each level multiplies its n by the result from below

The Recursion Tree

Another way to visualize this:

                    factorial(5)
                         ↓
                    5 * factorial(4)
                         ↓
                    5 * (4 * factorial(3))
                              ↓
                    5 * (4 * (3 * factorial(2)))
                                   ↓
                    5 * (4 * (3 * (2 * factorial(1))))
                                        ↓
                    5 * (4 * (3 * (2 * 1)))  ← Base case returns 1
                                        ↑
                    5 * (4 * (3 * 2))        ← 2 * 1 = 2
                              ↑
                    5 * (4 * 6)              ← 3 * 2 = 6
                         ↑
                    5 * 24                   ← 4 * 6 = 24
                      ↑
                    120                      ← 5 * 24 = 120

What Happens Without a Base Case?

Let's see what happens if we forget the base case:

def factorial_broken(n):
    """Factorial without base case - DON'T USE THIS!"""
    return n * factorial_broken(n - 1)  # Always recurses!

# This will crash
try:
    result = factorial_broken(5)
except RecursionError as e:
    print(f"Error: {e}")

Python Output:

Error: maximum recursion depth exceeded

Diagnostic Analysis:

The complete execution trace (first few and last few calls):

factorial_broken(5)
  → 5 * factorial_broken(4)
    → 4 * factorial_broken(3)
      → 3 * factorial_broken(2)
        → 2 * factorial_broken(1)
          → 1 * factorial_broken(0)
            → 0 * factorial_broken(-1)
              → -1 * factorial_broken(-2)
                ... [continues for ~1000 calls]
                  → -995 * factorial_broken(-996)
                    → -996 * factorial_broken(-997)
                      → RecursionError!

Root cause: No base case means the function never stops recursing. It keeps calling itself with smaller and smaller (eventually negative) numbers until Python's recursion limit is hit.

The fix: Always include a base case that will definitely be reached.

What Happens With Wrong Progress?

Another common mistake: the recursive call doesn't move toward the base case:

def factorial_wrong_progress(n):
    """Factorial with wrong recursive call - DON'T USE THIS!"""
    if n == 0 or n == 1:
        return 1
    return n * factorial_wrong_progress(n)  # BUG: n instead of n-1!

# This will also crash
try:
    result = factorial_wrong_progress(5)
except RecursionError as e:
    print(f"Error: {e}")

Python Output:

Error: maximum recursion depth exceeded in comparison

Diagnostic Analysis:

The complete execution trace (first few calls):

factorial_wrong_progress(5)
  → Is 5 == 0 or 5 == 1? No
  → Return 5 * factorial_wrong_progress(5)  ← Same n!

    factorial_wrong_progress(5)
      → Is 5 == 0 or 5 == 1? No
      → Return 5 * factorial_wrong_progress(5)  ← Still 5!

        factorial_wrong_progress(5)
          → Is 5 == 0 or 5 == 1? No
          → Return 5 * factorial_wrong_progress(5)  ← Forever 5!
            ... [infinite loop]

Root cause: The recursive call uses n instead of n - 1, so the problem never gets smaller. We keep calling factorial_wrong_progress(5) forever.

The fix: Ensure the recursive call makes progress toward the base case.

The Recursive Function Checklist

When writing or debugging a recursive function, verify:

✅ Base Case: - [ ] Is there at least one base case? - [ ] Does it return a value without recursing? - [ ] Is it checked before the recursive call? - [ ] Will every valid input eventually reach it?

✅ Recursive Case: - [ ] Does it call the function itself? - [ ] Is the argument simpler/smaller than the current one? - [ ] Does it make progress toward the base case? - [ ] Does it correctly combine the recursive result?

✅ Overall Logic: - [ ] Does the function return the correct type? - [ ] Are edge cases handled (empty input, zero, negative numbers)? - [ ] Is the recursion depth reasonable for expected inputs?

Complexity Analysis: Factorial

Time Complexity: O(n) - We make exactly n recursive calls (from n down to 1) - Each call does O(1) work (one multiplication) - Total: n × O(1) = O(n)

Space Complexity: O(n) - Call stack depth: n (one frame for each number from n to 1) - Each frame stores constant data (just n) - Total space: n stack frames = O(n)

Recurrence Relation: T(n) = T(n-1) + O(1) - Time to compute factorial(n) = time to compute factorial(n-1) + constant work - This solves to O(n) by telescoping: T(n) = T(n-1) + c = T(n-2) + 2c = ... = T(1) + (n-1)c = O(n)

The Call Stack Visualized

To truly understand recursion, you must understand the call stack—the mechanism Python uses to manage function calls. Recursion isn't magic; it's just function calls, and Python tracks them using a stack data structure.

What is the Call Stack?

The call stack is a stack (Last-In-First-Out data structure) that Python maintains to keep track of: - Which functions are currently executing - What their local variables are - Where to return to when each function finishes

Every time you call a function, Python: 1. Creates a stack frame containing the function's parameters and local variables 2. Pushes this frame onto the call stack 3. Executes the function's code 4. Pops the frame off the stack when the function returns 5. Resumes execution in the calling function

Visualizing the Stack: A Concrete Example

Let's trace factorial(4) and watch the call stack grow and shrink:

def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)

result = factorial(4)

Call Stack Evolution:

Step 1: Program starts, calls factorial(4)

┌─────────────────────┐
│ factorial(4)        │  ← Top of stack
│ n = 4               │
└─────────────────────┘

Step 2: factorial(4) calls factorial(3)

┌─────────────────────┐
│ factorial(3)        │  ← Top of stack
│ n = 3               │
├─────────────────────┤
│ factorial(4)        │
│ n = 4               │
│ waiting for result  │
└─────────────────────┘

Step 3: factorial(3) calls factorial(2)

┌─────────────────────┐
│ factorial(2)        │  ← Top of stack
│ n = 2               │
├─────────────────────┤
│ factorial(3)        │
│ n = 3               │
│ waiting for result  │
├─────────────────────┤
│ factorial(4)        │
│ n = 4               │
│ waiting for result  │
└─────────────────────┘

Step 4: factorial(2) calls factorial(1)

┌─────────────────────┐
│ factorial(1)        │  ← Top of stack
│ n = 1               │
├─────────────────────┤
│ factorial(2)        │
│ n = 2               │
│ waiting for result  │
├─────────────────────┤
│ factorial(3)        │
│ n = 3               │
│ waiting for result  │
├─────────────────────┤
│ factorial(4)        │
│ n = 4               │
│ waiting for result  │
└─────────────────────┘

Step 5: factorial(1) hits base case, returns 1

┌─────────────────────┐
│ factorial(1)        │  ← Returns 1, pops off
│ n = 1               │
│ return 1            │
└─────────────────────┘
        ↓ returns 1
┌─────────────────────┐
│ factorial(2)        │  ← Top of stack
│ n = 2               │
│ computes 2 * 1 = 2  │
├─────────────────────┤
│ factorial(3)        │
│ n = 3               │
│ waiting for result  │
├─────────────────────┤
│ factorial(4)        │
│ n = 4               │
│ waiting for result  │
└─────────────────────┘

Step 6: factorial(2) returns 2

┌─────────────────────┐
│ factorial(2)        │  ← Returns 2, pops off
│ n = 2               │
│ return 2            │
└─────────────────────┘
        ↓ returns 2
┌─────────────────────┐
│ factorial(3)        │  ← Top of stack
│ n = 3               │
│ computes 3 * 2 = 6  │
├─────────────────────┤
│ factorial(4)        │
│ n = 4               │
│ waiting for result  │
└─────────────────────┘

Step 7: factorial(3) returns 6

┌─────────────────────┐
│ factorial(3)        │  ← Returns 6, pops off
│ n = 3               │
│ return 6            │
└─────────────────────┘
        ↓ returns 6
┌─────────────────────┐
│ factorial(4)        │  ← Top of stack
│ n = 4               │
│ computes 4 * 6 = 24 │
└─────────────────────┘

Step 8: factorial(4) returns 24

┌─────────────────────┐
│ factorial(4)        │  ← Returns 24, pops off
│ n = 4               │
│ return 24           │
└─────────────────────┘
        ↓ returns 24

Stack is empty, result = 24

Key Observations:

Stack grows during descent: Each recursive call adds a frame
Maximum depth: 4 frames (for factorial(4) down to factorial(1))
Stack shrinks during ascent: Each return pops a frame
LIFO order: Last function called is first to return
Each frame is independent: Each has its own n value

Making the Call Stack Visible with Print Statements

We can instrument our code to see the call stack in action:

def factorial_verbose(n, depth=0):
    """Factorial with call stack visualization."""
    indent = "  " * depth  # Indent based on recursion depth
    print(f"{indent}→ factorial({n}) called")

    if n == 0 or n == 1:
        print(f"{indent}  Base case! Returning 1")
        return 1

    print(f"{indent}  Computing {n} * factorial({n-1})")
    result = n * factorial_verbose(n - 1, depth + 1)
    print(f"{indent}← factorial({n}) returning {result}")
    return result

print("Computing factorial(4):\n")
result = factorial_verbose(4)
print(f"\nFinal result: {result}")

Python Output:

Computing factorial(4):

→ factorial(4) called
  Computing 4 * factorial(3)
  → factorial(3) called
    Computing 3 * factorial(2)
    → factorial(2) called
      Computing 2 * factorial(1)
      → factorial(1) called
        Base case! Returning 1
      ← factorial(1) returning 1
    ← factorial(2) returning 2
  ← factorial(3) returning 6
← factorial(4) returning 24

Final result: 24

Analysis: The indentation shows the call stack depth. Notice: - Calls go deeper (more indentation) as we recurse down - Returns come back up (less indentation) as we unwind - The base case is the deepest point (most indented) - Each level waits for the level below it before returning

Python's Recursion Limit

Python has a built-in safety mechanism to prevent infinite recursion from crashing your program:

import sys

# Check the current recursion limit
print(f"Default recursion limit: {sys.getrecursionlimit()}")

# Try to exceed it
def infinite_recursion(n):
    return infinite_recursion(n + 1)

try:
    infinite_recursion(0)
except RecursionError as e:
    print(f"\nRecursionError caught: {e}")

Python Output:

Default recursion limit: 1000

RecursionError caught: maximum recursion depth exceeded

What this means: - Python allows a maximum of ~1000 nested function calls by default - This prevents infinite recursion from consuming all memory - If you hit this limit, it's usually a bug (missing base case or wrong progress) - You can increase it with sys.setrecursionlimit(), but this is rarely the right solution

When you might legitimately need more depth: - Processing very deep tree structures (e.g., deeply nested JSON) - Algorithms with deep recursion on large inputs (e.g., quicksort on 10,000 items)

Better solutions than increasing the limit: - Convert to iteration (we'll cover this in Module 1.4) - Use tail recursion patterns (Module 6.2) - Restructure the algorithm to reduce depth

Visualizing Stack Space Consumption

Let's measure how much memory the call stack uses:

import sys

def factorial_with_size(n):
    """Factorial that reports stack frame size."""
    if n == 0 or n == 1:
        return 1

    # Get the size of the current stack frame
    frame_size = sys.getsizeof(n)  # Size of parameter
    print(f"factorial({n}): frame size ≈ {frame_size} bytes")

    return n * factorial_with_size(n - 1)

print("Stack frame sizes:\n")
result = factorial_with_size(5)
print(f"\nTotal stack depth: 5 frames")
print(f"Approximate total stack space: 5 × ~28 bytes = ~140 bytes")

Python Output:

Stack frame sizes:

factorial(5): frame size ≈ 28 bytes
factorial(4): frame size ≈ 28 bytes
factorial(3): frame size ≈ 28 bytes
factorial(2): frame size ≈ 28 bytes
factorial(1): frame size ≈ 28 bytes

Total stack depth: 5 frames
Approximate total stack space: 5 × ~28 bytes = ~140 bytes

Key Insight: Each recursive call consumes stack space. For factorial(n), we use O(n) space on the call stack. This is why very deep recursion can cause problems—you can run out of stack space.

Comparing Recursion Depth: Linear vs Exponential

Not all recursive functions have the same call stack behavior. Let's compare:

def factorial(n):
    """Linear recursion: one recursive call per level."""
    if n <= 1:
        return 1
    return n * factorial(n - 1)

def fibonacci_naive(n):
    """Exponential recursion: two recursive calls per level."""
    if n <= 1:
        return n
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)

# Visualize the difference
print("Factorial(5) call tree:")
print("""
factorial(5)
  → factorial(4)
    → factorial(3)
      → factorial(2)
        → factorial(1)
          → base case

Maximum stack depth: 5
Total calls: 5
""")

print("\nFibonacci(5) call tree:")
print("""
                    fib(5)
                   /      \\
              fib(4)        fib(3)
             /      \\       /     \\
        fib(3)    fib(2) fib(2)  fib(1)
       /     \\    /    \\  /    \\
   fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
   /    \\
fib(1) fib(0)

Maximum stack depth: 5 (longest path)
Total calls: 15 (many redundant!)
""")

Key Differences:

Aspect	Factorial (Linear)	Fibonacci (Exponential)
Recursive calls per level	1	2
Call tree shape	Straight line	Binary tree
Total calls for n=5	5	15
Maximum stack depth	n	n
Time complexity	O(n)	O(2^n)

Important: Even though both have O(n) stack depth, fibonacci makes many more total calls because of the branching. This is why naive fibonacci is so slow—we'll fix this with memoization in Module 6.1.

The Call Stack in Error Messages

When recursion fails, Python's traceback shows you the call stack:

def buggy_factorial(n):
    """Factorial with a bug: forgets base case for n=0."""
    if n == 1:  # BUG: What about n=0?
        return 1
    return n * buggy_factorial(n - 1)

try:
    result = buggy_factorial(3)
    print(f"Result: {result}")
except RecursionError:
    print("RecursionError occurred!")
    print("\nLet's trace what happened:")
    print("buggy_factorial(3) → 3 * buggy_factorial(2)")
    print("buggy_factorial(2) → 2 * buggy_factorial(1)")
    print("buggy_factorial(1) → returns 1 ✓")
    print("So buggy_factorial(3) = 3 * 2 * 1 = 6 ✓")
    print("\nBut what about buggy_factorial(0)?")

try:
    result = buggy_factorial(0)
except RecursionError:
    print("\nbuggy_factorial(0) → 0 * buggy_factorial(-1)")
    print("buggy_factorial(-1) → -1 * buggy_factorial(-2)")
    print("buggy_factorial(-2) → -2 * buggy_factorial(-3)")
    print("... [continues forever until RecursionError]")
    print("\nThe bug: base case only checks n==1, not n<=1")

Python Output:

Result: 6

But what about buggy_factorial(0)?

buggy_factorial(0) → 0 * buggy_factorial(-1)
buggy_factorial(-1) → -1 * buggy_factorial(-2)
buggy_factorial(-2) → -2 * buggy_factorial(-3)
... [continues forever until RecursionError]

The bug: base case only checks n==1, not n<=1

Lesson: When you see a RecursionError, look at the traceback to see: 1. What function is recursing infinitely 2. What parameter values are being passed 3. Whether the values are moving toward or away from the base case

Practical Implications of the Call Stack

Understanding the call stack helps you:

Debug recursive functions: Trace the stack to see where things go wrong
Estimate space complexity: Each recursive call uses stack space
Avoid stack overflow: Design algorithms with reasonable recursion depth
Choose between recursion and iteration: Deep recursion → consider iteration
Optimize recursive algorithms: Techniques like tail recursion and memoization

Rule of thumb: If your recursion depth exceeds a few hundred levels, consider: - Is there a bug (infinite recursion)? - Can I convert to iteration? - Can I use tail recursion? - Can I restructure to reduce depth?

Lab: Trace Execution by Hand

The best way to internalize recursion is to trace recursive functions by hand. This lab will guide you through the process systematically.

Lab Setup

We'll trace three functions of increasing complexity: 1. Countdown: Simple linear recursion 2. Sum of list: Processing a data structure 3. Power function: Combining results

For each function, you'll: - Predict the output before running - Trace the call stack manually - Verify with actual execution - Identify the base case and recursive case

Exercise 1: Countdown Revisited

The Function:

def countdown(n):
    if n < 0:
        return
    print(n)
    countdown(n - 1)

Your Task: Trace countdown(3) by hand.

Step-by-Step Template:

Call: countdown(3)
├─ Check: Is 3 < 0? No
├─ Action: Print 3
├─ Recurse: countdown(2)
│  │
│  Call: countdown(2)
│  ├─ Check: Is 2 < 0? No
│  ├─ Action: Print 2
│  ├─ Recurse: countdown(1)
│  │  │
│  │  Call: countdown(1)
│  │  ├─ Check: Is 1 < 0? No
│  │  ├─ Action: Print 1
│  │  ├─ Recurse: countdown(0)
│  │  │  │
│  │  │  Call: countdown(0)
│  │  │  ├─ Check: Is 0 < 0? No
│  │  │  ├─ Action: Print 0
│  │  │  ├─ Recurse: countdown(-1)
│  │  │  │  │
│  │  │  │  Call: countdown(-1)
│  │  │  │  ├─ Check: Is -1 < 0? YES! BASE CASE
│  │  │  │  └─ Return (no print, no recurse)
│  │  │  │
│  │  │  └─ countdown(0) finishes
│  │  │
│  │  └─ countdown(1) finishes
│  │
│  └─ countdown(2) finishes
│
└─ countdown(3) finishes

Output: 3, 2, 1, 0

Verify:

def countdown(n):
    if n < 0:
        return
    print(n)
    countdown(n - 1)

print("Tracing countdown(3):")
countdown(3)

Python Output:

Tracing countdown(3):
3
2
1
0

Questions to Answer: 1. What is the base case? Answer: n < 0 2. What is the recursive case? Answer: countdown(n - 1) 3. How many stack frames are created? Answer: 5 (for n=3, 2, 1, 0, -1) 4. What is the maximum stack depth? Answer: 5

Exercise 2: Sum of a List

The Function:

def sum_list(lst):
    """Recursively sum all elements in a list."""
    if len(lst) == 0:  # Base case: empty list
        return 0
    first = lst[0]
    rest = lst[1:]
    return first + sum_list(rest)

Your Task: Trace sum_list([5, 3, 8]) by hand.

Manual Trace Template:

Call: sum_list([5, 3, 8])
├─ Check: Is len([5, 3, 8]) == 0? No
├─ Split: first = 5, rest = [3, 8]
├─ Recurse: 5 + sum_list([3, 8])
│  │
│  Call: sum_list([3, 8])
│  ├─ Check: Is len([3, 8]) == 0? No
│  ├─ Split: first = 3, rest = [8]
│  ├─ Recurse: 3 + sum_list([8])
│  │  │
│  │  Call: sum_list([8])
│  │  ├─ Check: Is len([8]) == 0? No
│  │  ├─ Split: first = 8, rest = []
│  │  ├─ Recurse: 8 + sum_list([])
│  │  │  │
│  │  │  Call: sum_list([])
│  │  │  ├─ Check: Is len([]) == 0? YES! BASE CASE
│  │  │  └─ Return: 0
│  │  │
│  │  ├─ Compute: 8 + 0 = 8
│  │  └─ Return: 8
│  │
│  ├─ Compute: 3 + 8 = 11
│  └─ Return: 11
│
├─ Compute: 5 + 11 = 16
└─ Return: 16

Result: 16

Verify:

def sum_list(lst):
    if len(lst) == 0:
        return 0
    first = lst[0]
    rest = lst[1:]
    return first + sum_list(rest)

print("Tracing sum_list([5, 3, 8]):")
result = sum_list([5, 3, 8])
print(f"Result: {result}")

Python Output:

Tracing sum_list([5, 3, 8]):
Result: 16

Questions to Answer: 1. What is the base case? Answer: Empty list (len(lst) == 0) 2. What is the recursive case? Answer: first + sum_list(rest) 3. How does the list get smaller? Answer: rest = lst[1:] removes the first element 4. What is returned by the base case? Answer: 0 (identity element for addition) 5. How many recursive calls? Answer: 4 (for lists of length 3, 2, 1, 0)

Exercise 3: Power Function

The Function:

def power(base, exponent):
    """Calculate base^exponent recursively."""
    if exponent == 0:  # Base case: anything^0 = 1
        return 1
    return base * power(base, exponent - 1)

Your Task: Trace power(2, 4) by hand (calculate 2^4 = 16).

Manual Trace:

Call: power(2, 4)
├─ Check: Is exponent (4) == 0? No
├─ Recurse: 2 * power(2, 3)
│  │
│  Call: power(2, 3)
│  ├─ Check: Is exponent (3) == 0? No
│  ├─ Recurse: 2 * power(2, 2)
│  │  │
│  │  Call: power(2, 2)
│  │  ├─ Check: Is exponent (2) == 0? No
│  │  ├─ Recurse: 2 * power(2, 1)
│  │  │  │
│  │  │  Call: power(2, 1)
│  │  │  ├─ Check: Is exponent (1) == 0? No
│  │  │  ├─ Recurse: 2 * power(2, 0)
│  │  │  │  │
│  │  │  │  Call: power(2, 0)
│  │  │  │  ├─ Check: Is exponent (0) == 0? YES! BASE CASE
│  │  │  │  └─ Return: 1
│  │  │  │
│  │  │  ├─ Compute: 2 * 1 = 2
│  │  │  └─ Return: 2
│  │  │
│  │  ├─ Compute: 2 * 2 = 4
│  │  └─ Return: 4
│  │
│  ├─ Compute: 2 * 4 = 8
│  └─ Return: 8
│
├─ Compute: 2 * 8 = 16
└─ Return: 16

Result: 16

Verify:

def power(base, exponent):
    if exponent == 0:
        return 1
    return base * power(base, exponent - 1)

print("Tracing power(2, 4):")
result = power(2, 4)
print(f"Result: {result}")
print(f"Verification: 2^4 = {2**4}")

Python Output:

Tracing power(2, 4):
Result: 16
Verification: 2^4 = 16

Questions to Answer: 1. What is the base case? Answer: exponent == 0, returns 1 2. What is the recursive case? Answer: base * power(base, exponent - 1) 3. How does the problem get smaller? Answer: exponent - 1 4. What is the time complexity? Answer: O(exponent) - we make exponent recursive calls 5. What is the space complexity? Answer: O(exponent) - call stack depth

Challenge Exercise: Trace a Buggy Function

The Function (contains a bug):

def mystery_function(n):
    """What does this function do? (Hint: it has a bug)"""
    if n == 1:
        return 1
    return n + mystery_function(n - 2)

Your Task: 1. Trace mystery_function(5) by hand 2. Identify what the function is trying to compute 3. Find the bug 4. Predict what happens with mystery_function(4)

Manual Trace of mystery_function(5):

Call: mystery_function(5)
├─ Check: Is 5 == 1? No
├─ Recurse: 5 + mystery_function(3)
│  │
│  Call: mystery_function(3)
│  ├─ Check: Is 3 == 1? No
│  ├─ Recurse: 3 + mystery_function(1)
│  │  │
│  │  Call: mystery_function(1)
│  │  ├─ Check: Is 1 == 1? YES! BASE CASE
│  │  └─ Return: 1
│  │
│  ├─ Compute: 3 + 1 = 4
│  └─ Return: 4
│
├─ Compute: 5 + 4 = 9
└─ Return: 9

Result: 9 (sum of odd numbers: 5 + 3 + 1)

Now trace mystery_function(4):

Call: mystery_function(4)
├─ Check: Is 4 == 1? No
├─ Recurse: 4 + mystery_function(2)
│  │
│  Call: mystery_function(2)
│  ├─ Check: Is 2 == 1? No
│  ├─ Recurse: 2 + mystery_function(0)
│  │  │
│  │  Call: mystery_function(0)
│  │  ├─ Check: Is 0 == 1? No
│  │  ├─ Recurse: 0 + mystery_function(-2)
│  │  │  │
│  │  │  Call: mystery_function(-2)
│  │  │  ├─ Check: Is -2 == 1? No
│  │  │  ├─ Recurse: -2 + mystery_function(-4)
│  │  │  │  ... [infinite recursion!]

The Bug: Base case only handles n == 1, not even numbers. When n is even, we skip over 1 and go negative, causing infinite recursion.

Verify:

def mystery_function(n):
    if n == 1:
        return 1
    return n + mystery_function(n - 2)

print("Testing mystery_function(5):")
print(f"Result: {mystery_function(5)}")

print("\nTesting mystery_function(4):")
try:
    result = mystery_function(4)
    print(f"Result: {result}")
except RecursionError:
    print("RecursionError! The function never reaches the base case.")
    print("Bug: Base case should be 'if n <= 1' to handle even numbers.")

Python Output:

Testing mystery_function(5):
Result: 9

Testing mystery_function(4):
RecursionError! The function never reaches the base case.
Bug: Base case should be 'if n <= 1' to handle even numbers.

The Fix:

def mystery_function_fixed(n):
    """Sum of numbers from n down to 1, stepping by 2."""
    if n <= 1:  # Fixed: handles both odd and even starting points
        return max(n, 0)  # Return n if positive, else 0
    return n + mystery_function_fixed(n - 2)

print("Fixed version:")
print(f"mystery_function_fixed(5) = {mystery_function_fixed(5)}")  # 5+3+1 = 9
print(f"mystery_function_fixed(4) = {mystery_function_fixed(4)}")  # 4+2 = 6
print(f"mystery_function_fixed(6) = {mystery_function_fixed(6)}")  # 6+4+2 = 12

Python Output:

Fixed version:
mystery_function_fixed(5) = 9
mystery_function_fixed(4) = 6
mystery_function_fixed(6) = 12

Lab Summary: Key Takeaways

What You've Learned:

How to trace recursion systematically:
Identify base case and recursive case
Track parameter values at each level
Follow the call stack down and back up
Compute results as the stack unwinds
Common patterns:
Linear recursion: One recursive call per level (countdown, factorial, sum)
Decreasing parameter: Problem gets smaller by subtracting/removing elements
Base case: The simplest case that returns without recursing
How to debug recursive functions:
Trace by hand with small inputs
Check if base case is reachable
Verify recursive case makes progress
Watch for off-by-one errors in base cases
The call stack mechanics:
Each call creates a stack frame
Frames stack up during descent
Frames pop off during ascent
Results combine as stack unwinds

Practice Problems (Try these on your own):

Trace factorial(3) by hand
Trace power(3, 3) by hand (calculate 3^3 = 27)
Write and trace a function count_down_by_two(n) that prints n, n-2, n-4, ... down to 0 or 1
Find and fix the bug in this function:

def sum_to_n(n):
    """Sum of 1 + 2 + ... + n (buggy version)"""
    if n == 0:
        return 0
    return sum_to_n(n - 1) + n

# What happens with sum_to_n(-5)?

Next Steps: In the next section (1.2), we'll write more recursive functions from scratch and develop intuition for when recursion is the right tool.

Chapter Summary and Key Concepts

The Journey: From Concept to Mastery

In this chapter, we've built a complete mental model of recursion from first principles:

Phase	What We Learned	Key Example
Concept	Recursion = solving problems by solving smaller versions	Counting doors in a hallway
Structure	Base case + recursive case	`countdown(n)`
Anatomy	Function signature, base case, recursive case	`factorial(n)`
Mechanics	The call stack: frames, LIFO, stack depth	Visualizing `factorial(4)`
Practice	Tracing execution by hand	Lab exercises

Core Principles

1. The Recursive Mindset - Break problems into smaller versions of themselves - Trust that the recursive call solves the smaller problem - Combine the recursive result with current work

2. The Two Essential Components - Base case: Stopping condition, returns without recursing - Recursive case: Calls itself with simpler input, makes progress toward base case

3. The Call Stack - Each function call creates a stack frame - Frames stack up during recursion (descent) - Frames pop off as functions return (ascent) - Maximum depth = deepest level of recursion

4. Common Pitfalls - Missing base case → infinite recursion - Base case not reachable → infinite recursion - Recursive call doesn't make progress → infinite recursion - Wrong base case return value → incorrect results

Pattern Recognition

Linear Recursion Pattern:

def linear_recursive(n):
    # Base case: simplest input
    if n <= BASE_VALUE:
        return BASE_RESULT

    # Recursive case: one recursive call
    return COMBINE(n, linear_recursive(n - STEP))

Examples: countdown, factorial, sum_list, power

Characteristics: - One recursive call per invocation - Call stack depth = O(n) - Time complexity often O(n)

Debugging Checklist

When your recursive function fails:

✅ Check the base case: - [ ] Does it exist? - [ ] Is it checked first? - [ ] Is it reachable from all valid inputs? - [ ] Does it return the correct value?

✅ Check the recursive case: - [ ] Does it call the function itself? - [ ] Is the argument simpler/smaller? - [ ] Does it make progress toward the base case? - [ ] Does it correctly combine the recursive result?

✅ Trace by hand: - [ ] Pick a small input (n=3 or similar) - [ ] Write out each function call - [ ] Track parameter values - [ ] Verify the base case is reached - [ ] Follow results back up the stack

Complexity Analysis Summary

Time Complexity: - Linear recursion with O(1) work per call: O(n) - Example: factorial, countdown, sum_list

Space Complexity: - Call stack depth: O(n) for linear recursion - Each frame stores constant data: O(1) - Total: O(n) space

Recurrence Relations: - Linear: T(n) = T(n-1) + O(1) → O(n) - We'll see more complex patterns in later modules

Looking Ahead

What's Next: - Module 1.2: Write more recursive functions from scratch - Module 1.3: Deep dive into base cases and recursive cases - Module 1.4: Compare recursion vs iteration

Skills You've Gained: - ✅ Understand what recursion is conceptually - ✅ Recognize the structure of recursive functions - ✅ Visualize the call stack - ✅ Trace recursive execution by hand - ✅ Debug common recursion errors

Skills Coming Next: - Writing recursive functions from scratch - Choosing the right base case - Handling multiple base cases - Converting between recursion and iteration

Final Thought

Recursion is not magic—it's just function calls. The "magic" comes from the elegant way recursive thinking maps to certain problem structures. As you practice, you'll develop intuition for when recursion clarifies a solution versus when it obscures it.

The key to mastering recursion: Trust the recursion. When writing the recursive case, assume the recursive call works correctly for the smaller problem. Your job is just to use that result to solve the current problem.

Now let's write some recursive functions from scratch! →